/*
275. H指数 II
这是 H指数 进阶问题：如果citations 是升序的会怎样？你可以优化你的算法吗？
*/

/* 普通的方法 */
class Solution
{
public:
    int hIndex(vector<int> &citations)
    {
        int n = citations.size();
        for(int i : citations) {
            if(i >= n) {
                return n;
            }
            n--;
        }
        return 0;
    }
};

/* 二分查找 */
class Solution
{
public:
    int hIndex(vector<int> &citations)
    {
        int high = citations.size() - 1;
        int low = 0;
        int n = high / 2;
        while(low <= high) {
            int count = citations.size() - n;
            if(count > citations[n]) {
                low = n + 1;
            } else if(count == citations[n]) {
                return count;
            } else {
                high = n - 1;
            }
            n = low + (high - low) / 2;
        }
        return citations.size() - low;
    }
};
